package practice1_100;

import java.util.Arrays;
import java.util.Date;
import java.util.Stack;
import java.util.Timer;

public class Practice5 {
    //两成for循环暴力法试试
    public String longestPalindrome(String s) {
        String maxLenght="";//
        int leftendIndex=0;
        int rightendIndex=0;
        String temp="";
        for (int left=0;left<s.length();left++){
            for(int right=left;right<s.length();right++){
//                temp=findMax(s,left,right);
                if(findMax(s,left,right)&&right-left>rightendIndex-leftendIndex){
//                    maxLenght=maxLenght.length()>=temp.length()?maxLenght:temp;
                    leftendIndex=left;
                    rightendIndex=right;
                }   
            }
        }
        return s.substring(leftendIndex,rightendIndex+1);
    }
    public boolean findMax(String s,int left,int right){
        int left1=left,right1=right;
        while (left<=right){
            if(s.charAt(left)!=s.charAt(right)){
               return false;
            }
            left++;
            right--;
        }
//        return s.substring(left1,right1+1);
        return true;
    }


    /**
     * 非暴力法，用动态规划做
     *  动态规划法，我们可以用空间换时间的策略，dpTable[n][m]记录nm是否为回文子串，用m-n记录最大值和n m，最后dpTable[n][m]为true且m-n最大，返回最长子串
     *  先初始化dpTable[n][n]=true
     *
     *  昨天对于dp算法，应当是先算出小区间的dpTable值，而不是直接先算大区间的dpTable值
      *
     *  dpTable[n][m]=dpTable[n+1][m-1]&&char[n]==char[m]
     *  当n+1=m时候，dpTable[n][m]=(char[n]==char[m])
     */

    public String longestPalindrome1(String s){
       char[] chars= s.toCharArray();
       boolean[][] dpTable=new boolean[chars.length][chars.length];
        for (int i = 0; i < dpTable.length ; i++) {
            dpTable[i][i]=true;
        }
       return dp(chars,dpTable,s);

    }

    private String dp(char[] chars,boolean[][] dpTable,String s) {
        int begin=0,end=0,temp=Integer.MIN_VALUE;
        for (int i = 1; i < dpTable.length; i++) {
            for (int j = 0; j < i ; j++) {
                if (chars[i]==chars[j]&&j+1!=i)
                    dpTable[j][i]=dpTable[j+1][i-1];
                if (chars[i]==chars[j]&&j+1==i)
                    dpTable[j][i]=true;
                if(temp<i-j&&dpTable[j][i]==true){
                    begin=j;
                    end=i;
                    temp=i-j;
                }
            }
        }
        return s.substring(begin,end+1);
    }

    public static void main(String[] args) {
        long date = new Date().getTime();
        Practice5 practice5=new Practice5();
        String ss="aaaaabb";
        String s=practice5.longestPalindrome1(ss);
        System.out.println(s);
        System.out.println(new Date().getTime()-date);
    }
}
